package main

/**
A B C D E
C B A D E

第一步圈定要翻转的范围
第二步执行翻转

1->2->3->4->5 k=2
1.确定翻转范围,对[head,node)节点进行翻转，示例中head指向1，node指向3，翻转范围是[1,3)
2.翻转上步的子链表，返回翻转后的首节点2(2->1->3)，注意翻转后head 1变为子链表尾结点
3.子链表尾节点指向下一个翻转范围的首节点，进入递归
4.返回首节点
![](http://cdn.bsummer.cn/20191204123134.png)
*/
import . "local/algorithm/util"

// reverseKGroup返回按k个节点翻转后的首元素
func reverseKGroup(head *ListNode, k int) *ListNode {
	node := head
	for i := 0; i < k; i++ {
		//注意是先判断node==nil 再next 当node==nil时，node.Next无法取地址
		if node == nil {
			return head //当无法明确返回什么时，以一个典型例子来测试，比如以1->2 k=3为例，直接返回值为1的node，即head
		}
		node = node.Next
	}
	newhead := reverse(head, node)     // 翻转的范围 [head,node),newhead为翻转后头节点，head变为子链表尾节点
	head.Next = reverseKGroup(node, k) //这一步容易出错 head至prevnode(node 前一个节点)翻转后，head变为最后一个节点，head会转向下一个区间的第一个节点
	return newhead
}

// reverse 对[first,last)链表翻转并返回翻转后的首节点
func reverse(first *ListNode, last *ListNode) *ListNode {
	prev := last
	current := first
	for current != last {
		tmp := current.Next
		current.Next = prev
		prev = current
		current = tmp
	}

	//此时current==last，prev指向翻转后的首节点
	return prev
}

func main() {
	list := GenerateLinkedList([]int{1, 2})
	newList := reverseKGroup(list, 2)
	PrintLinkedList(newList)
}

func reverseKgroup(head *ListNode, k int) *ListNode {
	node := head
	for i := 0; i < k; i++ {
		if node == nil {
			return head
		}
		node = node.Next
	}

	newhead := reverse(head, node)
	head.Next = reverseKgroup(node, k)
	return newhead
}

func reverse(first, last *ListNode) *ListNode {
	prev := last
	curr := first
	for curr != last {
		tmp := curr.Next
		curr.Next = prev
		prev = curr
		curr = tmp
	}
	return curr
}
